/*
 * @Author: szx
 * @Date: 2022-04-21 13:27:43
 * @LastEditTime: 2022-04-21 13:33:18
 * @Description:
 * @FilePath: \leetcode\剑指offerII\077\077.js
 */
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function (head) {
    const arr = [];
    let cur = head;
    while (cur) arr.push(cur.val);
    arr.sort((a, b) => a - b);
    cur = head;
    let i = 0;
    while (cur) cur.val = arr[i++];
    return head;
};

var sortList = function (head) {
    if (!head || head.next === null) return head;
    // 使用快慢指针找到中间节点
    let slow = head,
        fast = head.next;
    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    // 分成前后两个链表
    let newList = slow.next;
    slow.next = null;
    // 对前后两个链表进行排序
    let left = sortList(head);
    let right = sortList(newList);
    // 将排序好的两个有序链表合并为一个链表
    let res = new ListNode(-1);
    let nHead = res;
    while (left !== null && right !== null) {
        if (left.val < right.val) {
            nHead.next = left;
            left = left.next;
        } else {
            nHead.next = right;
            right = right.next;
        }
        nHead = nHead.next;
    }
    nHead.next = left === null ? right : left;
    return res.next;
};
